题解：P10904 [蓝桥杯 2024 省 C] 挖矿

思路：

定义两个数组 $a$ 和 $b$，其中 $a$ 存输入为正数的情况，$b$ 存输入为负数时负数的绝对值，在定义两个变量 $cnt$ 存起点矿石的情况，$ans$ 存最多挖矿石几个矿石不包含起点矿石的情况。

输入完后将 $a$ 数组与 $b$ 数组排序。

排序过后枚举情况，共有两种情况，第一种完全不向右侧挖掘，第二种向右走两次向左走一次，每次枚举完情况后更新 $ans$ 的值。

最终的结果为在输入中 $ans+cnt$。

代码：

#include<bits/stdc++.h>
using namespace std; 
#define LL long long
#define itn int
#define ull unsigned long long
vector<LL>a,b;// 分别存储正数和负数(取绝对值后)
int main(){
	LL n,m;
	cin>>n>>m;
	LL cnt=0;// 计算坐标为 0 的矿洞数量
	a.push_back(0);// 下标从 1 开始 
	b.push_back(0);
	for(LL i=0;i<n;i++){
		LL sr;
		cin>>sr;
		if(sr==0)cnt++;// 坐标为 0 的矿洞直接计算
		else if(sr>0)a.push_back(sr);// 正数放入 a 数组
		else b.push_back(-sr);// 负数取绝对值后放入 b 数组
		
	}
	sort(a.begin()+1,a.end());
	sort(b.begin()+1,b.end());
	LL ans=0,pos1=b.size()-1,pos2=b.size()-1;
	for(LL i=0;i<=a.size()-1;i++){// 枚举情况 
		LL x=m-a[i];
		if(x<0)continue;
		while(b[pos1]>x/2)pos1--; 
		ans=max(ans,i+pos1);
//		cout<<ans<<" 1 \n";
		// 完全不向右侧挖掘
		x=m-a[i]*2;
		if(x<0)continue;
		while(b[pos2]>x)pos2--; 
		ans=max(ans,i+pos2);
//		cout<<ans<<" 2 \n";
		// 向右走两次向左走一次
	}
//	cout<<ans<<" "<<cnt<<"\n";
	cout<<ans+cnt;
	return 0;
}